import { WeightedUnionFind } from "./加权并查集"

// 路径压缩后的加权并查集
class WeightedUnionFindComPress extends WeightedUnionFind {
    private recordStack: number[]; // 用于记录需要压缩的触点
    constructor(size: number) {
        super(size);
        this.recordStack = [];
    }
    // 快速查找方法--->压缩
    protected quickFind(elem: number): number {
        while (elem !== this.unionList[elem]) {
            elem = this.unionList[elem];
            this.recordStack.push(elem);// 记录需要压缩路径的触点
        }
        // 压缩路径
        let curr: number | undefined = undefined;
        while ((curr = this.recordStack.pop()) != null) {
            this.unionList[curr] = elem;
        }
        return elem;
    }
}


// 测试用例
const uf: WeightedUnionFindComPress = new WeightedUnionFindComPress(9);
console.log('开始测试： WeightedUnionFindComPress');
uf.union([4, 3]);
uf.union([3, 8]);
uf.union([6, 5]);
uf.union([9, 4]);
uf.union([2, 1]);
uf.union([8, 9]);
uf.union([5, 0]);
uf.union([5, 0]);
uf.union([7, 2]);
uf.union([6, 1]);
uf.union([1, 0]);
uf.union([6, 7]);
console.log(uf.getCount()); // 2
console.log(uf.isConnected([2, 6])); // true
console.log(uf.isConnected([4, 5])); // false
console.log(uf.isConnected([1, 8])); // false
uf.union([1, 8]);
console.log(uf.getCount()); // 1
console.log(uf.isConnected([4, 5])); // true